package cm.oneDimensional;

import java.util.Arrays;
import java.util.OptionalInt;

public class HouseRobberDemo {
    /**
     * https://leetcode.com/problems/house-robber/
     * 状态转移方程：dp[i] = max(dp[i-1],dp[i-2])
     */
    public int rob(int[] nums) {
        if (nums==null || nums.length==0){
            return 0;
        }

        if (nums.length<=2){
            return Arrays.stream(nums).max().getAsInt();
        }

        int[] dp = new int[2];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);

        int tmp;
        for (int i = 2; i < nums.length; i++) {
            tmp = Math.max(dp[0]+nums[i],dp[1]);
            dp[0] = dp[1];
            dp[1] = tmp;
        }

        return dp[1];
    }



    public static void main(String[] args) {
        HouseRobberDemo obj = new HouseRobberDemo();
//        int[] nums = {2,7,9,3,1};
        int[] nums = {2,1,1,2};
        System.out.println(obj.rob(nums));
    }
}
